交互题最好玩♂了!(雾)
题意简述:有一个 个数的排列,每次询问 得到 的值,最多使用 次询问,猜出这个序列。
思路:
看到最多 次询问,我们想到了什么?凭我们的直觉,这就是明摆着的提示要询问 和 啊!那怎么询问呢?
我们知道对于 ,,可以得到下面结论:
结论:。
简单证明:
在知道这个性质之后,我们就可以想到询问的方法:
设 为 中最大的数的下标(大小可根据上面的结论判断),每次询问 和 ,判断两个结果哪个更大,更新偏小的那个下标的值及最大数的下标。
最后剩下一个 没有值,由于数列是 的一个排列,因此这个最大的数就是 。
总询问次数 。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n, a[N], ma = 1;
int ask(int x, int y) {
int _;
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &_);
return _;
}
int main() {
scanf("%d", &n);
for(int i=2;i<=n;i++) {
int _1 = ask(ma, i);
int _2 = ask(i, ma);
if(_1 > _2) {
a[ma] = _1;
ma = i;
}
else a[i] = _2;
}
a[ma] = n;
putchar('!');
for(int i=1;i<=n;i++) printf(" %d", a[i]);
return 0;
}